import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution432 {

    static class Pair{
        String s;
        int time;

        public Pair(String s, int time) {
            this.s = s;
            this.time = time;
        }
    }

    Map<String,Integer> map=new HashMap<>();
    PriorityQueue<Pair> queue1=new PriorityQueue<>(Comparator.comparingInt(a -> a.time));
    PriorityQueue<Pair> queue2=new PriorityQueue<>(Comparator.comparingInt(a -> -a.time));

    public Solution432() {

    }

    public void inc(String key) {
        map.put(key,map.getOrDefault(key,0)+1);
        queue1.offer(new Pair(key,map.get(key)));
        queue2.offer(new Pair(key,map.get(key)));
    }

    public void dec(String key) {
        map.put(key,map.get(key)-1);
        if (map.get(key)==0){
            map.remove(key);
            return;
        }
        queue1.offer(new Pair(key,map.get(key)));
        queue2.offer(new Pair(key,map.get(key)));
    }

    public String getMaxKey() {
        if (map.size()==0){
            return "";
        }
        while (!map.containsKey(queue2.peek().s) || queue2.peek().time!=map.get(queue2.peek().s)){
            queue2.poll();
        }
        return queue2.peek().s;
    }

    public String getMinKey() {
        if (map.size()==0){
            return "";
        }
        while (!map.containsKey(queue1.peek().s) || queue1.peek().time!=map.get(queue1.peek().s)){
            queue1.poll();
        }
        return queue1.peek().s;
    }

    public static void main(String[] args) {
        Solution432 solution432=new Solution432();
        solution432.inc("hello");
        solution432.inc("hello");
        System.out.println(solution432.getMaxKey());
        System.out.println(solution432.getMinKey());
        solution432.inc("leet");
        System.out.println(solution432.getMaxKey());
        System.out.println(solution432.getMinKey());
    }
}
